class Node:
    def __init__(self, val, c):
        self.val = val
        self.neighbors = {}
        self.c = c


class MapSum(object):

    def __init__(self):
        self.tree = Node('#', 0)
        self.d = {}

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: None
        """
        if key not in self.d:
            self.d[key] = val
            diff = val
        else:
            diff = val - self.d[key]
            self.d[val] = val
        node = self.tree
        for w in key:
            if w in node.neighbors:
                node = node.neighbors[w]
                node.c += diff
            else:
                new_node = Node(w, diff)
                node.neighbors[w] = new_node
                node = new_node

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        node = self.tree
        for w in prefix:
            if w in node.neighbors:
                node = node.neighbors[w]
            else:
                return 0
        return node.c
